package lbj.cyw.dp;

/*
* 152. 最大乘积子数组
* */
public class MaxProduct152 {
    public int maxProduct(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int n=nums.length;
        int[] minF=new int[n];
        int[] maxF=new int[n];
        minF[0]=nums[0];
        maxF[0]=nums[0];
        int max=nums[0];
        for(int i=1;i<n;i++){
            minF[i]=Math.min(nums[i],Math.min(minF[i-1]*nums[i],maxF[i-1]*nums[i]));
            maxF[i]=Math.max(nums[i],Math.max(minF[i-1]*nums[i],maxF[i-1]*nums[i]));
            max=Math.max(max,maxF[i]);
        }
        return max;
    }
}
